package main

import (
	"fmt"
	"sort"
)

/**
执行用时：12 ms, 在所有 Go 提交中击败了45.23%的用户
内存消耗：2.8 MB, 在所有 Go 提交中击败了31.81%的用户
 */
func fourSum(nums []int, target int) [][]int {

	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})

	res := [][]int{}
	for i := 0; i < len(nums); i++ {
		if i > 0 && nums[i] == nums[i - 1] { continue }
		for j := i + 1; j < len(nums); j++ {
			if j > i + 1 && nums[j] == nums[j - 1] { continue }
			for k, u := j + 1, len(nums) - 1; k < u; k++ {
				if k > j + 1 && nums[k] == nums[k - 1] { continue }
				for k < u - 1 && nums[i] + nums[j] + nums[k] + nums[u - 1] >= target { u-- }
				if nums[i] + nums[j] + nums[k] + nums[u] == target {
					res = append(res, []int{nums[i], nums[j], nums[k], nums[u]})
				}
			}
		}
	}
	return res
}

func main() {

	nums := []int{1, 0, -1, 0, -2, 2}
	fmt.Println(fourSum(nums, 0))
}
